package leetcode100

// TODO 前缀和 [经典] 【-】 和为 K 的子数组
// TODO https://leetcode.cn/problems/subarray-sum-equals-k/solution/dai-ni-da-tong-qian-zhui-he-cong-zui-ben-fang-fa-y/

func subarraySum(nums []int, k int) int {
	count := 0
	// 前缀和的哈希表,其 k 为前缀和, 其 v 为此前缀和出现的次数。初始放入0:1键值对, 标识前缀和为 0 的有 1 次
	hash := map[int]int{0: 1}
	prefixSum := 0

	for i := 0; i < len(nums); i++ {
		prefixSum += nums[i] // 前缀和改变
		if hash[prefixSum-k] > 0 {
			count += hash[prefixSum-k]
		}
		// 如果 key=prefixSum 对应的 value 加 1
		hash[prefixSum]++
	}
	return count
}
